class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int sign = n < 0 ? 1 : 0;
        long long num = n;
        if (num < 0) {
            num = -num;
        }
        double ans = 1.0;
        double y = x;

        while (num) {
            if (num & 1) {
                ans *= y;
            }
            y *= y;
            num >>= 1;
        }
        return sign ? 1.0 / ans : ans;
    }
};
